/**
 * gcc version 11.2.0 (Ubuntu 11.2.0-19ubuntu1)
*/

#include<iostream>
#include<algorithm>

/**
 * 冒泡排序 O(N平方) 
*/
template<class T>
void bubbleSort(T* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size - 1; j++) {
            if (arr[i] > arr[j]) {
                std::swap(arr[i], arr[j]);
            }
        }
    }
}

/**
 * 快速排序 辅助函数
 */
template<class T>
T paritition(T* arr, int low, int high) {
    T pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];

        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }

    arr[low] = pivot;
    return low;
}

/**
 * 快速排序 O(NlogN)
*/
template<class T>
void quickSort(T* arr, int low, int high) {
    if (low < high) {
        T pivot = paritition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

/**
 * 基数排序 O(N) 此函数仅对 uint 进行排序
*/
void iRadixSort(int* arr, int size) {
    // 计算最大位数
    int max = arr[0];              
    for (int i = 1; i < size; ++i) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    int base = 1;
    int ten = 10;
    while (max >= ten) {
        max /= 10;
        base++;
    }

    //开始排序
    int *tempArr = new int[size];
    int countArr[10];
    int radix = 1;
    for (int i = 1; i <= base; i++) {
        for (int j = 0; j < 10; j++) {
            countArr[j] = 0;
        }
        for (int j = 0; j < size; j++) {
            int k = (arr[j] / radix) % 10; 
            countArr[k]++;
        }
        for (int j = 1; j < 10; j++) {
            countArr[j] = countArr[j - 1] + countArr[j];
        }
        for (int j = size - 1; j >= 0; j--) {
            int k = (arr[j] / radix) % 10;
            tempArr[countArr[k] - 1] = arr[j];
            countArr[k]--;
        }
        for (int j = 0; j < size; j++) {
            arr[j] = tempArr[j];
        }
        radix *= 10;
    }

    delete[] tempArr;
}

/**
 * 打印数组
*/
template<class T>
void printArray(T* arr, int size) {
    for (int i = 0; i < size; i++) {
        std::cout << *(arr++) << " " << std::flush;
    }
    std::cout << std::endl;
}

/**
 * 主函数
*/
int main() {
    // 基数排序
    int arr[10] = { 91 ,27 ,73 ,46 ,55 ,64 ,37 ,82 ,19 ,106 };
    std::cout << "Before sort , the array is \t\t" << std::flush;
    printArray(arr, 10);
    iRadixSort(arr, 10);
    std::cout << "After radix sort , the array is \t" << std::flush;
    printArray(arr, 10);

    // 冒泡排序
    double arr_d[] = { 9.1 ,2.8 ,7.3 ,4.6 ,5.5 ,6.4 ,3.7 ,8.2 ,1.9 ,10.0 };
    std::cout << "\nBefore sort , the array is \t\t" << std::flush;
    printArray(arr_d, 10);
    bubbleSort(arr_d, 10);
    std::cout << "After bubble sort , the array is \t" << std::flush;
    printArray(arr_d, 10);

    // 快速排序
    char arr_c[10] = { 'e' ,'c' ,'a' ,'b' ,'f' ,'e' ,'d' ,'g' ,'l' ,'x' };
    std::cout << "\nBefore sort , the array is \t\t" << std::flush;
    printArray(arr_c, 10);
    quickSort(arr_c, 0, 9);
    std::cout << "After quick sort , the array is \t" << std::flush;
    printArray(arr_c, 10);

    // std::sort 排序
    int arr_i[10] = { 9 ,2 ,7 ,4 ,5 ,6 ,3 ,8 ,1 ,10 };
    std::cout << "\nBefore sort , the array is \t\t" << std::flush;
    printArray(arr_i, 10);
    std::sort(arr_i, arr_i + 10);
    std::cout << "After std::sort , the array is \t" << std::flush;
    printArray(arr_i, 10);

    return 0;
}